package pers.qianyu.month_202101.date_20210130;

/**
 * 74. 数组中唯一只出现一次的数字
 * https://www.acwing.com/problem/content/70/
 *
 * @author mizzle rain
 * @date 2021年1月30日13:03:49
 */
public class FindNumberAppearingOnce {
    /**
     * 大佬做法：
     * 状态机：三个状态之后回归原来状态
     * (0, 0) -1-> (1, 0) -1-> (0, 1) -1-> (0, 0)
     */
    public int findNumberAppearingOnce(int[] nums) {
        int ones = 0, twos = 0;
        for (int x : nums) {
            ones = (ones ^ x) & ~twos;
            twos = (twos ^ x) & ~ones;
        }
        return ones;
    }

    /**
     * 常规做法，统计个位上 1 出现的次数
     */
    public int findNumberAppearingOnce2(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int num : nums) {
                count += (num >> i) & 1;
            }
            if (count % 3 != 0) res += 1 << i;
        }
        return res;
    }
}